package slidingWindow;

import org.junit.Test;

import java.util.*;

/*
 *@description
 *@author hkfan
 *@version 1.0
 *@create 2025/5/28 15:19
 */
public class LeetCode_30 {

    @Test
    public void test(){
        List<Integer> list = findSubstring("barfoothefoobarman", new String[]{"foo", "bar"});
        for (Integer i : list) {
            System.out.println(i);
        }
    }

    public List<Integer> findSubstring(String s, String[] words) {
        //1. 定义变量
        int m = words[0].length(),n=words.length;
        List<Integer> res = new ArrayList<>();
        Map<String,Integer> map = new HashMap<>();
        //2. 录入map
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0)+1);
        }
        //3. 外层循环遍历
        for (int i = 0; i < m; i++) {
            int l=i,r=i+m-1;
            Map<String,Integer> tempMap = initMap(map);
            for (; r <s.length() ; r+=m) {
                String word = s.substring(r-m+1,r+1);
                if (map.get(word)!=null){       //存在
                    if (tempMap.get(word)!=null){
                        if (tempMap.get(word)>1){
                            tempMap.put(word,tempMap.get(word)-1);
                        }else {
                            tempMap.remove(word);
                        }
                        if (tempMap.isEmpty()){
                            res.add(l);
                        }
                        if (r-l+1==n*m){
                            String temp = s.substring(l,l+m);
                            tempMap.put(temp,tempMap.getOrDefault(temp,0)+1);
                            l+=m;
                        }
                    }else {
                        //右移，直到有为止
                        while (true){
                            String temp = s.substring(l,l+m);
                            if (temp.equals(word)){
                                l+=m;
                                break;
                            }else {
                                tempMap.put(temp,tempMap.getOrDefault(temp,0)+1);
                                l+=m;
                            }
                        }
                    }

                }else {
                    l=r+1;
                    tempMap = initMap(map);
                }
            }
        }
        return res;

    }

    private Map<String, Integer> initMap(Map<String, Integer> map) {
        HashMap<String, Integer> res = new HashMap<>();
        for (String s : map.keySet()) {
            res.put(s,map.get(s));
        }
        return res;
    }


}
